% Function : K-Means clustering algorithms
% Parameter:
%   V: values of points(vector)
%   k: number of clusters(scalar)
% Return:
%   C: values of centers(vector)
%   L: labels of each element(vector)
function [C, L] = KMeans(V, k)
    % check input argument
    if nargin ~= 2
        error('Usage: KMeans(V, k)');
    end

    if ~isvector(V)
        error('KMeans: V must be a vector');
    end

    n = numel(V);

    % initialize center values
    v = sort(V, 'descend');
    C = zeros(1, k);
    for i = 1 : k
        t = i * (n + 1) / (k + 1);
        l = floor(t);
        u = ceil(t);
        if l == u
            C(i) = v(l);
        else
            C(i) = v(l) * (t - l) + v(u) * (u - t);
        end
    end
    L = zeros(1, n);

    count = 0;
    while true
        b = L;              % backup of labels for each elements
        s = zeros(1, k);    % sum of each center
        c = zeros(1, k);    % counter of each center
        for i = 1 : n
            d = abs(C - V(i));
            l = find(d == min(d));
            l = l(1);

            % update sum and counter
            s(l) = s(l) + V(i);
            c(l) = c(l) + 1;
            % update labels of each element
            L(i) = l;
        end

        % centers no longer change
        if all(b == L)
            break;
        end

        % update center values
        for i = 1 : k
            if c(i) == 0
                C(i) = 0;
            else
                C(i) = s(i) / c(i);
            end
        end

        count = count + 1;
        if count > 100
            break;
        end
    end
end
